{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Smallest Common Element in All Rows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #binary-search #counting #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #二分查找 #计数 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestCommonElement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出所有行中最小公共元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m x n</code>&nbsp;的矩阵&nbsp;<code>mat</code>，其中每一行的元素均符合&nbsp;<strong>严格递增</strong> 。请返回 <em>所有行中的&nbsp;<strong>最小公共元素</strong>&nbsp;</em>。</p>\n",
    "\n",
    "<p>如果矩阵中没有这样的公共元素，就请返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>mat = [[1,2,3],[2,3,4],[2,3,5]]\n",
    "<strong>输出：</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= mat[i][j] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>mat[i]</code>&nbsp;已按严格递增顺序排列。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-smallest-common-element-in-all-rows](https://leetcode.cn/problems/find-smallest-common-element-in-all-rows/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-smallest-common-element-in-all-rows](https://leetcode.cn/problems/find-smallest-common-element-in-all-rows/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]', '[[1,2,3],[2,3,4],[2,3,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        hashmap = {}\n",
    "\n",
    "        for i in mat:\n",
    "            for j in i:\n",
    "                if j not in hashmap:\n",
    "                    hashmap[j] = 1\n",
    "                else:\n",
    "                    hashmap[j] += 1\n",
    "        res = float('inf')\n",
    "        for i in hashmap:\n",
    "            if hashmap[i] == len(mat):\n",
    "                res = min(res, i)\n",
    "\n",
    "        if res == float('inf'):\n",
    "            return -1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        res_arr = set(mat[0])\n",
    "        for i in range(1,len(mat)):   \n",
    "            res_arr = res_arr.intersection(set(mat[i]))\n",
    "        \n",
    "        return (min(res_arr) if res_arr else -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        res_arr = set(mat[0])\n",
    "        for i in range(1,len(mat)):   \n",
    "            res_arr = res_arr.intersection(set(mat[i]))\n",
    "            if not res_arr:\n",
    "                return -1\n",
    "        \n",
    "        return (min(res_arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        res_arr = set(mat[0])\n",
    "        for i in range(1,len(mat)):   \n",
    "            res_arr = res_arr.intersection(set(mat[i]))\n",
    "            if not res_arr:\n",
    "                return -1\n",
    "        \n",
    "        return (min(res_arr) if res_arr else -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        temp_set = None\n",
    "        for i in mat:\n",
    "            if temp_set is None:\n",
    "                temp_set = set(i)\n",
    "            else:\n",
    "                temp_set = temp_set.intersection(set(i))\n",
    "        \n",
    "        if temp_set:\n",
    "            return min(temp_set)\n",
    "        else:\n",
    "            return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        hashmap = {}\n",
    "        for item in mat:\n",
    "            for i in item:\n",
    "                if i in hashmap:\n",
    "                    hashmap[i]+=1\n",
    "                else:\n",
    "                    hashmap[i]=1\n",
    "        min = 10000\n",
    "        flag = False\n",
    "        for k in hashmap:\n",
    "            if hashmap[k]==len(mat):\n",
    "                flag = True\n",
    "                if k<min:\n",
    "                    min=k\n",
    "        if not flag:\n",
    "            return -1   \n",
    "        return min\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        cnt = defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                cnt[mat[i][j]] += 1\n",
    "        ans = inf\n",
    "        for key in cnt:\n",
    "            if cnt[key] == m:\n",
    "                ans = min(ans, key)\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        vals = [mat[i][0] for i in range(m)]\n",
    "        max_ = max(vals)\n",
    "\n",
    "        h = [(mat[i][0], i, 0) for i in range(m)]\n",
    "        heapq.heapify(h)\n",
    "\n",
    "        while True:\n",
    "            if h[0][0] == max_:\n",
    "                return max_\n",
    "            \n",
    "            _, i, j = heapq.heappop(h)\n",
    "            if j == n - 1:\n",
    "                return -1\n",
    "\n",
    "            v = mat[i][j + 1]\n",
    "            max_ = max(max_, v)\n",
    "            heapq.heappush(h, (v, i, j + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        res = set(mat[0])\n",
    "        for line in mat:\n",
    "            # print(res)\n",
    "            res = res.intersection(set(line))\n",
    "        if not res:\n",
    "            return -1\n",
    "        return min(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        mi = -1\n",
    "        for m1 in mat[0]:\n",
    "            c = 1\n",
    "            for j in range(1, len(mat)):\n",
    "                if m1 in mat[j]:\n",
    "                    c += 1\n",
    "\n",
    "            if c == len(mat):\n",
    "                return m1\n",
    "\n",
    "        return mi\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        freq = defaultdict(int)\n",
    "        for ptr in range(n):\n",
    "            for row in range(m):\n",
    "                freq[mat[row][ptr]] += 1\n",
    "                if freq[mat[row][ptr]] == m:\n",
    "                    return mat[row][ptr]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        n = len(mat)\n",
    "        arr = [i for j in mat for i in j ]\n",
    "        c = collections.Counter(arr)\n",
    "        res = 10 ** 5\n",
    "        for k, v in c.items():\n",
    "            if v == n:\n",
    "                res = min(res, k)\n",
    "        return res if res != 10 ** 5 else -1\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        hashmap={}\n",
    "        for i in mat:\n",
    "            for j in i:\n",
    "                hashmap[j]=hashmap.get(j,0)+1\n",
    "        for a,b in hashmap.copy().items():\n",
    "            if b!=len(mat):\n",
    "                del hashmap[a]\n",
    "        if hashmap.keys():\n",
    "            return min(hashmap.keys())\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        cnt = {}\n",
    "        ans = mat[-1][-1] + 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = mat[i][j]\n",
    "                if x not in cnt:\n",
    "                    cnt[x] = 1\n",
    "                else:\n",
    "                    cnt[x] += 1\n",
    "                if cnt[x] == m:\n",
    "                    return x\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        # 各种利用python特性的奇技淫巧\n",
    "        s = set(mat[0])\n",
    "        for i in mat[1:]:\n",
    "            s &= set(i)\n",
    "        return min(list(s)) if s else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        #获取公共区间\n",
    "        interval=[]\n",
    "        for i,row in enumerate(mat):\n",
    "            if i ==0:\n",
    "                interval=row\n",
    "            else:\n",
    "                for x in interval:\n",
    "                    if x not in row:\n",
    "                        interval.remove(x)\n",
    "        if len(interval)==0:\n",
    "            return -1  \n",
    "        return interval[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "      def erfen(nums, l, r, tar):\n",
    "        if l>r:\n",
    "          return False\n",
    "        if nums[l] == tar or nums[r] == tar:\n",
    "          return True\n",
    "        if nums[l]>tar or nums[r]<tar:\n",
    "          return False\n",
    "        mid = (l+r)//2\n",
    "        if nums[mid] == tar:\n",
    "          return True\n",
    "        if nums[mid]>tar:\n",
    "          return erfen(nums, l, mid-1, tar)\n",
    "        return erfen(nums, mid+1, r, tar)\n",
    "      for num in mat[0]:\n",
    "        flag = False\n",
    "        for i in range(1, len(mat)):\n",
    "          if erfen(mat[i], 0, len(mat[0])-1, num):\n",
    "            continue\n",
    "          flag = True\n",
    "          break\n",
    "        if not flag:\n",
    "          return num\n",
    "      return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        hashmap={}\n",
    "        for i in mat:\n",
    "            for j in i:\n",
    "                hashmap[j]=hashmap.get(j,0)+1\n",
    "        for a,b in hashmap.copy().items():\n",
    "            if b!=len(mat):\n",
    "                del hashmap[a]\n",
    "        if hashmap.keys():\n",
    "            return min(hashmap.keys())\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        def commonSequence(seq_1: List[int], seq_2: List[int]):\n",
    "            res = []\n",
    "            i = 0\n",
    "            j = 0\n",
    "\n",
    "            while i < len(seq_1) and j < len(seq_2):\n",
    "                if seq_1[i] == seq_2[j]:\n",
    "                    res.append(seq_1[i])\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                elif seq_1[i] < seq_2[j]:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            return res\n",
    "\n",
    "        if not mat:\n",
    "            return -1\n",
    "        dp = mat[0]\n",
    "        for i in range(1, len(mat)):\n",
    "            dp = commonSequence(dp, mat[i])\n",
    "\n",
    "        if dp:\n",
    "            return dp[0]\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        for i in mat:\n",
    "            for j in i:\n",
    "                if dic.get(j):\n",
    "                    dic[j] = dic[j] + 1\n",
    "                else:\n",
    "                    dic[j] = 1\n",
    "        for i in dic.keys():\n",
    "            if dic[i] == len(mat):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        s = set(mat[0])\n",
    "        for i in mat[1:]:\n",
    "            s &= set(i)\n",
    "        return min(list(s)) if s else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        #获取公共区间\n",
    "        interval=[]\n",
    "        for i,row in enumerate(mat):\n",
    "            if i ==0:\n",
    "                interval=row\n",
    "            else:\n",
    "                for x in interval:\n",
    "                    if x not in row:\n",
    "                        interval.remove(x)\n",
    "        if len(interval)==0:\n",
    "            return -1  \n",
    "        return interval[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        #直观想法是维护一个最小公共元素行列表\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        row=Counter(mat[0])\n",
    "        ans=-1\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                row[mat[i][j]]+=1\n",
    "                if row[mat[i][j]]==m:\n",
    "                    if ans==-1: ans=mat[i][j]\n",
    "                    else: ans=min(ans,mat[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        counter = collections.defaultdict(int)\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                counter[mat[i][j]] += 1\n",
    "\n",
    "        ret = -1\n",
    "        for k, v in counter.items():\n",
    "            if v == len(mat) and (ret == -1 or k < ret):\n",
    "                ret = k\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        dit = {}\n",
    "        m = len(mat)\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j] not in dit:\n",
    "                    dit[mat[i][j]] = 0\n",
    "                dit[mat[i][j]] += 1\n",
    "                if dit[mat[i][j]] == m:\n",
    "                    return mat[i][j]\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        path = set(mat[0])\n",
    "        for i in range(1, len(mat)):\n",
    "            path &= set(mat[i])\n",
    "        return min(path) if path else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        n,m = len(mat), len(mat[0])\n",
    "        cur_max,cnt= 0, 0\n",
    "        pos = [0]*n\n",
    "        while True:\n",
    "            for i in range(n):\n",
    "                pos[i] = bisect.bisect_left(mat[i], cur_max, lo=pos[i]) # 找到当前行中cur_max的位置\n",
    "                if pos[i]==m: \n",
    "                    return -1\n",
    "                if cur_max == mat[i][pos[i]]:\n",
    "                    cnt +=1\n",
    "                    if cnt == n: return cur_max\n",
    "                else:\n",
    "                    cnt = 1 # 重置\n",
    "                cur_max = mat[i][pos[i]] # 更新\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        res_arr = set(mat[0])\n",
    "        for i in range(1,len(mat)):   \n",
    "            res_arr = res_arr.intersection(set(mat[i]))\n",
    "            if not res_arr:\n",
    "                return -1\n",
    "        \n",
    "        return (min(res_arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        res_arr = set(mat[0])\n",
    "        for i in range(1,len(mat)):   \n",
    "            res_arr = res_arr & set(mat[i])\n",
    "            if not res_arr:\n",
    "                return -1\n",
    "        \n",
    "        return (min(res_arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for j in range(n):\n",
    "            i = 1\n",
    "            while i < m:\n",
    "                L, R = 0, n-1\n",
    "                flag = False\n",
    "                while L <= R:\n",
    "                    mid = (L + R) // 2\n",
    "                    if mat[i][mid] == mat[0][j]:\n",
    "                        flag = True\n",
    "                        break\n",
    "                    elif mat[i][mid] > mat[0][j]:\n",
    "                        R = mid - 1\n",
    "                    else:\n",
    "                        L = mid + 1\n",
    "                if flag:    i += 1\n",
    "                else:   break\n",
    "            if i == m:  return mat[0][j]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "\n",
    "        for num in mat[0]:\n",
    "            flag = False\n",
    "            for i in range(1, n):\n",
    "                t = bisect.bisect_left(mat[i], num)\n",
    "                if not (0 <= t < m and mat[i][t] == num):\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                return num\n",
    "        return -1\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        res_arr = list()\n",
    "        for x in range(len(mat)):\n",
    "            res_arr += mat[x]\n",
    "        \n",
    "        res_arr.sort(reverse=True)\n",
    "        new_res_dict ={v:k for k,v in dict(Counter(res_arr)).items()}    \n",
    "        return new_res_dict.get(len(mat),-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        path = set(mat[0])\n",
    "        for i in range(1, len(mat)):\n",
    "            path &= set(mat[i])\n",
    "        return min(path) if path else -1\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        dit = {}\n",
    "        m = len(mat)\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j] not in dit:\n",
    "                    dit[mat[i][j]] = 0\n",
    "                dit[mat[i][j]] += 1\n",
    "                if dit[mat[i][j]] == m:\n",
    "                    return mat[i][j]\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        # ans=set(mat[0][::-1])\n",
    "        # n=len(mat)\n",
    "        # m=len(mat[0])\n",
    "        # # print(ans)\n",
    "        # #求公共元素\n",
    "        # for i in range(1,n):\n",
    "        #     ans=ans&set(mat[i])\n",
    "        # if not ans:\n",
    "        #     return -1\n",
    "        # res=inf\n",
    "        # for i in ans:\n",
    "        #     res=min(res,i)\n",
    "        # return res\n",
    "        for num in mat[0]:\n",
    "            cnt=0\n",
    "            for i in range(1,len(mat)):\n",
    "                ind=bisect.bisect_left(mat[i],num)\n",
    "                if ind>=len(mat[0]) or mat[i][ind]!=num:\n",
    "                    break\n",
    "                cnt+=1\n",
    "            if cnt==len(mat)-1:\n",
    "                return num\n",
    "        return -1\n",
    "             \n",
    "\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        my_set = set(mat[0])\n",
    "        for temp in mat:\n",
    "            my_set = my_set & set(temp)\n",
    "        return min(my_set) if my_set else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        def common_sequence(seq1, seq2):\n",
    "            seq = []\n",
    "            i = 0\n",
    "            j = 0\n",
    "            while i < len(seq1) and j < len(seq2):\n",
    "                if seq1[i] == seq2[j]:\n",
    "                    seq.append(seq1[i])\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                elif seq1[i] < seq2[j]:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            return seq\n",
    "        dp = mat[0]\n",
    "        for i in range(1, len(mat)):\n",
    "            dp = common_sequence(dp, mat[i])\n",
    "        if dp:\n",
    "            return dp[0]\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        dit = {}\n",
    "        n = len(mat)\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j] not in dit:\n",
    "                    dit[mat[i][j]] = 0\n",
    "                dit[mat[i][j]] += 1\n",
    "                if dit[mat[i][j]] == n:\n",
    "                    return mat[i][j]\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        n = len(mat)\n",
    "        inter = set(mat[0])\n",
    "        for i in range(1, n):\n",
    "            inter = inter.intersection(set(mat[i]))\n",
    "        result = sorted(list(inter))\n",
    "        return result[0] if result else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        h = [(mat[i][0], i, 0) for i in range(m)]\n",
    "        m = max(mat[i][0] for i in range(m))\n",
    "        heapq.heapify(h)\n",
    "        while h and h[0][0] < m:\n",
    "            v, i, j = heapq.heappop(h)\n",
    "            j += 1\n",
    "            if j == n:\n",
    "                return -1\n",
    "            heapq.heappush(h, (mat[i][j], i, j))\n",
    "            m = max(m, mat[i][j])\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        s1 = set(mat[0])\n",
    "        for i in range(1, len(mat)):\n",
    "            s1 = s1.intersection(mat[i])\n",
    "            if len(s1) == 0:\n",
    "                return -1\n",
    "        return min(s1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat), len(mat[0])\n",
    "        dic = {}\n",
    "        for vec in mat:\n",
    "            for item in vec:\n",
    "                if item not in dic:\n",
    "                    dic[item] = 1\n",
    "                else:\n",
    "                    dic[item] +=1\n",
    "        for key in dic:\n",
    "            if dic[key] == m:\n",
    "                return key\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        row=Counter(mat[0])\n",
    "        ans=-1\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                row[mat[i][j]]+=1\n",
    "                if row[mat[i][j]]==m:\n",
    "                    if ans==-1: ans=mat[i][j]\n",
    "                    else: ans=min(ans,mat[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        return self.answer_1(mat)\n",
    "\n",
    "    def answer_1(self, mat):\n",
    "        storage = defaultdict(int)\n",
    "\n",
    "        min_value, max_value = float(\"inf\"), float(\"-inf\")\n",
    "        row_len, col_len = len(mat), len(mat[0])\n",
    "\n",
    "        for row_index in range(row_len):\n",
    "            for col_index in range(col_len):\n",
    "                value = mat[row_index][col_index]\n",
    "                storage[value] += 1\n",
    "                min_value = min(min_value, value)\n",
    "                max_value = max(max_value, value)\n",
    "\n",
    "        for index in range(min_value, max_value + 1):\n",
    "            if storage[index] == row_len:\n",
    "                return index\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        num_times = collections.defaultdict(int)\n",
    "        for row in mat:\n",
    "            for num in row:\n",
    "                num_times[num] += 1\n",
    "        \n",
    "        min_num = 100000\n",
    "        for k, v in num_times.items():\n",
    "            if v == len(mat):\n",
    "                min_num = min(min_num, k)\n",
    "        \n",
    "        return min_num if min_num != 100000 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 逐行查找\n",
    "    def smallestCommonElement1(self, mat: List[List[int]]) -> int:\n",
    "        if not mat:\n",
    "            return -1\n",
    "        n = len(mat)\n",
    "        counts = collections.defaultdict(int)\n",
    "        for nums in mat:\n",
    "            for val in nums:\n",
    "                counts[val] += 1\n",
    "        for k,v in counts.items():\n",
    "            if v == n:\n",
    "                return k\n",
    "        return -1\n",
    "        \n",
    "    # 二分查找\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        '''\n",
    "        通过二分查找，顺序判断矩阵的公共最小值\n",
    "        '''\n",
    "        if not mat:\n",
    "            return -1\n",
    "        n, m = len(mat), len(mat[0])\n",
    "\n",
    "        def bisect_right(nums, val):\n",
    "            '''二分查找，返回数组中大于等于val的值，如果val为最大返回None'''\n",
    "            if not nums:\n",
    "                return\n",
    "            m = len(nums)\n",
    "            l, r = 0, m - 1\n",
    "            while l <= r:\n",
    "                mid = (r - l) // 2 + l\n",
    "                if val == nums[mid]:\n",
    "                    return val\n",
    "                if val < nums[mid]:\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return nums[l] if l < m else None\n",
    "\n",
    "        '''矩阵左上角的为最小值，match为匹配的行数，cur_row为滚动匹配的行'''\n",
    "        base = mat[0][0]\n",
    "        match = 0\n",
    "        cur_row = 1\n",
    "        while match <= m:\n",
    "            val = bisect_right(mat[cur_row % n], base)\n",
    "            if not val:\n",
    "                return -1\n",
    "            elif val != base:\n",
    "                base = val\n",
    "                match = 1\n",
    "            elif match == m:\n",
    "                return val\n",
    "            cur_row += 1\n",
    "            match += 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        cnt = Counter()\n",
    "        for i in range(m):\n",
    "            vis = set()\n",
    "            for j in range(n):\n",
    "                if mat[i][j] not in vis:\n",
    "                    vis.add(mat[i][j])\n",
    "                    cnt[mat[i][j]] += 1\n",
    "                    if cnt[mat[i][j]] == m:\n",
    "                        return mat[i][j]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        # count = defaultdict(int)\n",
    "        # min_num = -1\n",
    "        # num_row = len(mat)\n",
    "        all_exist_val = set()\n",
    "        black_list = []\n",
    "        for idx, row in enumerate(mat):\n",
    "            temp = set()\n",
    "            for ele in row:\n",
    "                if ele in black_list:\n",
    "                    continue\n",
    "                # count[ele] += 1\n",
    "                if idx == 0:\n",
    "                    all_exist_val.add(ele)\n",
    "                temp.add(ele)\n",
    "            black = all_exist_val.difference(temp)\n",
    "            all_exist_val = all_exist_val.difference(black)\n",
    "            black_list += list(black)\n",
    "        if len(all_exist_val) == 0:\n",
    "            return -1\n",
    "        \n",
    "        return min(list(all_exist_val))\n",
    "        # for ele in count.keys():\n",
    "        #     if count[ele] == num_row:\n",
    "        #         if min_num != -1:\n",
    "        #             min_num = min(min_num, ele)\n",
    "        #         else:\n",
    "        #             min_num = ele\n",
    "        # return min_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        e_map = {}\n",
    "        for i in mat:\n",
    "            for j in i:\n",
    "                if e_map.get(j):\n",
    "                    e_map[j] += 1\n",
    "                else:\n",
    "                    e_map[j] = 1\n",
    "\n",
    "        for i in e_map.keys():\n",
    "            if e_map[i] == len(mat):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        for mat1 in mat:\n",
    "            for i in mat1:\n",
    "                dic[i] = dic.get(i,0)+1\n",
    "        for i in dic:\n",
    "            if dic.get(i) == len(mat):\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        vals = [mat[i][0] for i in range(m)]\n",
    "        max_ = max(vals)\n",
    "\n",
    "        h = [(mat[i][0], i, 0) for i in range(m)]\n",
    "        heapq.heapify(h)\n",
    "\n",
    "        while True:\n",
    "            if h[0][0] == max_:\n",
    "                return max_\n",
    "            \n",
    "            _, i, j = heapq.heappop(h)\n",
    "            if j == n - 1:\n",
    "                return -1\n",
    "\n",
    "            v = mat[i][j + 1]\n",
    "            max_ = max(max_, v)\n",
    "            heapq.heappush(h, (v, i, j + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        dic = defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dic[mat[i][j]] += 1\n",
    "        \n",
    "        min_val = 10e4 + 1\n",
    "        for k, v in dic.items():\n",
    "            if v == m:\n",
    "                min_val = min(min_val, k)\n",
    "        return min_val if min_val != 10e4 + 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        kt=mat[0][0]\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        idx=[0]*m\n",
    "        while(1):\n",
    "            k=kt\n",
    "            flag=0\n",
    "            for dxi in range(m):\n",
    "                dx=idx[dxi]\n",
    "                if dx>=n:\n",
    "                    return -1\n",
    "                if mat[dxi][dx]>k:\n",
    "                    k=mat[dxi][dx]\n",
    "                elif mat[dxi][dx]==k:\n",
    "                    flag+=1\n",
    "                    continue\n",
    "                else:\n",
    "                    idx[dxi]+=1\n",
    "            if k==kt and flag==m:\n",
    "                return k  \n",
    "            else:\n",
    "                kt=k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        counter = collections.defaultdict(int)\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                counter[mat[i][j]] += 1\n",
    "\n",
    "        ret = -1\n",
    "        for k, v in counter.items():\n",
    "            if v == len(mat) and (ret == -1 or k < ret):\n",
    "                ret = k\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        # mi = -1\n",
    "        # for m1 in mat[0]:\n",
    "        #     c = 1\n",
    "        #     for j in range(1, len(mat)):\n",
    "        #         if m1 in mat[j]:\n",
    "        #             c += 1\n",
    "\n",
    "        #     if c == len(mat):\n",
    "        #         return m1\n",
    "\n",
    "        # return mi\n",
    "        ref = set(mat[0])\n",
    "        print(ref)\n",
    "        for i in range(1,len(mat)):\n",
    "            ref &= set(mat[i])\n",
    "            print(ref)\n",
    "        return min(ref) if ref else -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        bucket = [0 for _ in range(10005)]\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                bucket[mat[i][j]] += 1\n",
    "\n",
    "        for i in range(len(bucket)):\n",
    "            if bucket[i] == len(mat):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        map_ = {}\n",
    "        for i in mat:  #遍历每一行\n",
    "            for j in i:#遍历第i行的每一列\n",
    "                if map_.get(j):#如果哈希表中可以找到第i行第j列的数\n",
    "                    map_[j] = map_[j] + 1#个数加1\n",
    "                else:\n",
    "                    map_[j] = 1#找不到则加入到哈希表中，个数为1\n",
    "        for i in map_.keys():\n",
    "            if map_[i] == len(mat):#最小公共数，哈希表中该数的个数为行数\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        row=Counter(mat[0])\n",
    "        ans=-1\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                row[mat[i][j]]+=1\n",
    "                if row[mat[i][j]]==m:\n",
    "                    if ans==-1: ans=mat[i][j]\n",
    "                    else: ans=min(ans,mat[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        hashmap={}\n",
    "        for i in mat:\n",
    "            for j in i:\n",
    "                hashmap[j]=hashmap.get(j,0)+1\n",
    "        for a,b in hashmap.copy().items():\n",
    "            if b!=len(mat):\n",
    "                del hashmap[a]\n",
    "        if hashmap.keys():\n",
    "            return min(hashmap.keys())\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        hashdict = defaultdict(int)\n",
    "        for i in range(len(mat)):\n",
    "            for ai in mat[i]:\n",
    "                if hashdict[ai]==i:\n",
    "                    hashdict[ai] += 1\n",
    "        for k, v in list(hashdict.items()):\n",
    "            if v!=len(mat):\n",
    "                del hashdict[k]\n",
    "        if len(hashdict)==0:\n",
    "            return -1\n",
    "        newdict = dict(sorted(hashdict.items(), key=lambda x:x[0]))\n",
    "        keys = list(newdict.keys())\n",
    "        # print(hashdict, newdict)\n",
    "        return keys[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        h_dict = dict()\n",
    "        for row in range(len(mat)):\n",
    "            for col in range(len(mat[0])):\n",
    "                h_dict[mat[row][col]] = h_dict.get(mat[row][col], []) + [row]\n",
    "        h_dict = {k: v for k, v in h_dict.items() if len(v) == len(mat)}\n",
    "        return sorted(list(h_dict.keys()))[0] if h_dict else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        h_dict = dict()\n",
    "        for row in range(len(mat)):\n",
    "            for col in range(len(mat[0])):\n",
    "                h_dict[mat[row][col]] = h_dict.get(mat[row][col], []) + [row]\n",
    "        h_dict = {k: v for k, v in h_dict.items() if len(v) == len(mat)}\n",
    "        return sorted(list(h_dict.keys()))[0] if h_dict else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        h_dict = dict()\n",
    "        for row in range(len(mat)):\n",
    "            for col in range(len(mat[0])):\n",
    "                h_dict[mat[row][col]] = h_dict.get(mat[row][col], []) + [row]\n",
    "        h_dict = {k: v for k, v in h_dict.items() if len(v) == len(mat)}\n",
    "        return sorted(list(h_dict.keys()))[0] if h_dict else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        h_dict = dict()\n",
    "        for row in range(len(mat)):\n",
    "            for col in range(len(mat[0])):\n",
    "                h_dict[mat[row][col]] = h_dict.get(mat[row][col], []) + [row]\n",
    "        h_dict = {k: v for k, v in h_dict.items() if len(v) == len(mat)}\n",
    "        return sorted(list(h_dict.keys()))[0] if h_dict else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestCommonElement(self, mat: List[List[int]]) -> int:\n",
    "        res_arr = list()\n",
    "        for x in range(len(mat)):\n",
    "            res_arr += mat[x]\n",
    "           \n",
    "        res_dict = dict(sorted((Counter(res_arr)).items(), key=lambda x:(x[1],x[0]), reverse=True))      \n",
    "        new_res_dict ={v:k for k,v in res_dict.items()}        \n",
    "\n",
    "        return new_res_dict.get(len(mat),-1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
